package com.data.structure.node;

/**
 * @author zflu
 * 二叉树
 * Created by lucky on 2019-01-17.
 */
public class BinaryTree {

    private BNode root;

    public BinaryTree(){
        root = null;
    }

    /**
     * 查找二叉树
     * @param value
     * @return
     */
    public BNode find(int value){
        BNode current = root;
        if(current == null){
            return null;
        }
        //如果没有找到就一直循环
        while (current.value != value){
            //如果是在左节点
            if(current.value > value){
                current = current.leftNode;
            }else{
                current = current.rightNode;
            }

            //如果取到的节点为null
            if(current == null){
                return null;
            }
        }
        return current;
    }

    /**
     * 插入二叉树
     * @param value
     */
    public void insert(int value){
        BNode newNode = new BNode();
        newNode.value = value;
        if(root == null){
            root = newNode;
        }else{
            BNode current = root;
            BNode parent;
            while (true){
                parent = current;
                if(value < current.value){
                    current = current.leftNode;
                    if(current == null){
                        parent.leftNode = newNode;
                        newNode.parent = parent;
                        return;
                    }
                }else{
                    current = current.rightNode;
                    if(current == null){
                        parent.rightNode = newNode;
                        newNode.parent = parent;
                        return;
                    }
                }
            }
        }
    }

    public boolean delete(int value){
        BNode current = root;
        //是否是左节点
        boolean isLeftNode = true;
        //如果根节点为null
        if(current == null){
            return false;
        }
        while (current.value != value){
            if(value < current.value){
                //找左节点
                isLeftNode = true;
                current = current.leftNode;
            }else{
                //找右节点
                isLeftNode = false;
                current = current.rightNode;
            }
            if(current == null){
                return false;
            }
        }
        //要删除的节点没有左右节点，直接将该节点赋值为null
        if(current.leftNode == null && current.rightNode == null){
            return delNoChild(current,isLeftNode);
        }else if(current.leftNode != null && current.rightNode != null){
            return delTwoChild(current,isLeftNode);
        }else{
            return delOneChild(current,isLeftNode);
        }
    }

    /**
     * 删除没有左右子节点的节点
     * @param node
     * @param isLeftNode
     * @return
     */
    private boolean delNoChild(BNode node, boolean isLeftNode){
        if(node == root){
            root = null;
            return true;
        }
        if(isLeftNode){
            node.parent.leftNode = null;
        }else{
            node.parent.rightNode = null;
        }
        return true;
    }

    private boolean delOneChild(BNode node, boolean isLeftNode){
        //判断是左节点还是右节点
        if(node.leftNode == null){
            //在右边
            if(node == root){
                root = node.rightNode;
                node.parent = null;
                return true;
            }
            if(isLeftNode){
                node.parent.leftNode = node.rightNode;
            }else{
                node.parent.rightNode = node.rightNode;
            }
            //将它设置为null
            node.rightNode.parent = null;
        }else{
            //在左边
            if(node == root){
                root = node.leftNode;
                node.parent = null;
                return true;
            }
            if(isLeftNode){
                node.parent.leftNode = node.leftNode;
            }else{
                node.parent.rightNode = node.leftNode;
            }
            //将它设置为null
            node.leftNode.parent = null;
        }
        return true;
    }

    private boolean delTwoChild(BNode node, boolean isLeftNode){
        BNode successNode = getSuccessNode(node);
        if(node == root){
            successNode.leftNode = root.leftNode;
            root = successNode;
            return true;
        }
        if(isLeftNode){
            node.parent.leftNode = successNode;
        }else{
            node.parent.rightNode = successNode;
        }
        //3.设置删除节点的左节点为 中继节点的左节点
        successNode.leftNode = node.leftNode;
        return true;
    }

    private BNode getSuccessNode(BNode delNode){
        BNode success = delNode;
        //拿到右节点
        BNode current = delNode.rightNode;
        //获取中继节点
        while (current != null){
            success = current;
            current = current.leftNode;
        }
        //如果中继节点不是删除节点的右节点
        if(success != delNode.rightNode){
            //1.将中继节点的右节点替换为中继节点父节点的左节点
            success.parent.leftNode = success.rightNode;
            if(success.rightNode != null){
                //将中继节点的右节点 的父节点设置为中继节点的父节点
                success.rightNode.parent = success.parent;
            }
            //2.将中继节点的右节点 替换为要被删除节点的右子节点
            success.rightNode = delNode.rightNode;
        }
        return success;
    }

    /**
     * 遍历二叉树
     * @param traverseType
     */
    public void traverse(int traverseType){
        switch (traverseType){
            case 1:
                traverseBefore(root);
                break;
            case 2:
                traverseMiddle(root);
                break;
            case 3:
                traverseAfter(root);
                break;
            default:
                traverseMiddle(root);
                break;
        }
    }

    /**
     * 前序
     */
    private void traverseBefore(BNode before){
        if(before != null){
            System.out.println(before.value);
            traverseBefore(before.leftNode);
            traverseBefore(before.rightNode);
        }
    }

    /**
     * 中序
     * @param middle
     */
    private void traverseMiddle(BNode middle) {
        if(middle != null){
            traverseMiddle(middle.leftNode);
            System.out.println(middle.value);
            traverseMiddle(middle.rightNode);
        }
    }

    /**
     * 后序
     * @param after
     */
    private void traverseAfter(BNode after) {
        if(after != null){
            traverseAfter(after.leftNode);
            traverseAfter(after.rightNode);
            System.out.println(after.value);
        }
    }

    /**
     * 查找树的最小值
     * 根据二叉树的规则，最小值在没有子节点的左节点
     * @return
     */
    public BNode findMin(){
        BNode current = root;
        BNode parent = root;
        while (current != null){
            parent = current;
            current = parent.leftNode;
        }
        return parent;
    }

    /**
     * 查找树的最大值
     * 根据二叉树的规则，最大值在没有子节点的右节点
     * @return
     */
    public BNode findMax(){
        BNode current = root;
        BNode parent = root;
        while (current != null){
            parent = current;
            current = parent.rightNode;
        }
        return parent;
    }

    public class BNode {

        private int value;

        private BNode parent;

        private BNode leftNode;

        private BNode rightNode;

        public void display(){
            System.out.println("{value:"+ value +"}");
        }
    }
}
